package regular;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author NGUYEN VAN QUYET
 * 
 */
public class DistributedReach {

	public static void main(String[] args) {

		GraphQuery gq = getAutomaton0();

		Rvec[] rvset1 = localEval1(gq);
		Rvec[] rvset2 = localEval2(gq);
		Rvec[] rvset3 = localEval3(gq);
		Rvec[] RVset = concat(rvset1, rvset2);
		RVset = concat(RVset, rvset3);

		String privousVertex = "";
		for (Rvec r : RVset) {
			if (!r.v.equals(privousVertex))
				System.out.print("\n" + r.v + ": ");
			privousVertex = r.v;
			System.out.print("(" + r.u + ",");
			for (BoolFormula b : r.value)
				if (b.boolVar == null)
					System.out.print(b.value);
				else
					System.out.print(b.boolVar.toString());

			System.out.print(")");
		}
		System.out.print("\n\n");

		// perform evaluation on coordinator site
		boolean answer = evalDG(RVset, gq);
		System.out.print(answer);
	}

	public static GraphQuery getAutomaton() {
		// construct the query automaton
		VertexQ vq0 = new VertexQ("4");
		VertexQ vq1 = new VertexQ("DB");
		VertexQ vq2 = new VertexQ("HR");
		VertexQ vq3 = new VertexQ("12");

		vq0.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq1.stateName), new EdgeQ(vq2.stateName)));
		vq1.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq1.stateName), new EdgeQ(vq3.stateName)));
		vq2.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq2.stateName), new EdgeQ(vq3.stateName)));

		ArrayList<VertexQ> Vq = new ArrayList<VertexQ>(Arrays.asList(vq0, vq1,
				vq2, vq3));
		GraphQuery gq = new GraphQuery(Vq, vq0, vq3);
		return gq;
	}

	public static GraphQuery getAutomaton0() {
		// construct the query automaton
		VertexQ vq0 = new VertexQ("4");
		VertexQ vq1 = new VertexQ("DB");
		VertexQ vq3 = new VertexQ("7");

		vq0.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq1.stateName)));
		vq1.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq3.stateName)));

		ArrayList<VertexQ> Vq = new ArrayList<VertexQ>(Arrays.asList(vq0, vq1,
				vq3));
		GraphQuery gq = new GraphQuery(Vq, vq0, vq3);
		return gq;
	}

	public static GraphQuery getAutomaton1() {
		// construct the query automaton
		VertexQ vq0 = new VertexQ("2124");
		VertexQ vq1 = new VertexQ("Film & Animation");
		VertexQ vq2 = new VertexQ("Entertainment");
		VertexQ vq3 = new VertexQ("949");

		vq0.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq1.stateName), new EdgeQ(vq2.stateName)));
		vq1.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq1.stateName), new EdgeQ(vq3.stateName)));
		vq2.childrenState = new ArrayList<EdgeQ>(Arrays.asList(new EdgeQ(
				vq2.stateName), new EdgeQ(vq3.stateName)));

		ArrayList<VertexQ> Vq = new ArrayList<VertexQ>(Arrays.asList(vq0, vq1,
				vq2, vq3));
		GraphQuery gq = new GraphQuery(Vq, vq0, vq3);
		return gq;
	}

	// A BFS based function to check whether s can reach t
	public static boolean isReachable(ArrayList<VertexD> Vd, VertexD s,
			VertexD t) {
		if (s.equals(t))
			return true;

		// Create a queue for BFS
		Queue<VertexD> queue = new LinkedList<VertexD>();
		s.visit = true;
		queue.add(s);

		while (!queue.isEmpty()) {
			VertexD v = queue.poll();

			for (EdgeD e : v.neighbors) {
				// If this neighbor is the target vertex, then return true
				if (e.target.equals(t))
					return true;
				// Else, continue to do BFS
				if (e.target.visit == false) {
					queue.add(e.target);
					e.target.visit = true;
				}
			}
		}
		return false;
	}

	public static boolean evalDG(Rvec[] RVset, GraphQuery gq) {
		boolean answer = false;

		Vertex s = new Vertex(gq.us.stateName);
		Vertex t = new Vertex(gq.ut.stateName);

		// construct dependence graph from RVset
		ArrayList<VertexD> Vd = new ArrayList<VertexD>();
		String preVertex = null;
		for (Rvec r : RVset) {
			if (!r.v.equals(preVertex)) {
				// - false
				if (r.value.get(0).value == true
						|| r.value.get(0).boolVar != null) {
					VertexD vd = new VertexD(r.v, r.u, r.value);
					Vd.add(vd);
					preVertex = r.v;
				}
			}
		}

		// Terminal state
		VertexD vdt = new VertexD(t.name, t.name, new ArrayList<BoolFormula>(
				Arrays.asList(new BoolFormula(true))));

		int idStartVd = -1;

		boolean checkVdt = false;
		ArrayList<VertexD> listRemove = new ArrayList<VertexD>();
		// set neighbors
		for (VertexD v : Vd) {
			for (BoolFormula f : v.label)
				if (f.value == true) {
					if (!v.name.equals(vdt.name)) // final state in in-node
						v.neighbors.add(new EdgeD(vdt));
					else
						checkVdt = true;
				} else if (f.boolVar != null) {
					// int index = Vd.indexOf(f.boolVar.v);
					VertexD target = getVertexD(f.boolVar.v, Vd);
					// if (index >= 0) {
					// VertexD target = Vd.get(index);
					if (target != null)
						v.neighbors.add(new EdgeD(target));
					// }
				}
			if (v.name.equals(s.name))
				idStartVd = Vd.indexOf(v);

			// if don't have neighbor then remove
			if (v.neighbors.size() == 0 && !v.name.equals(vdt.name))
				listRemove.add(v);
		}

		// remove all node don't match of any state in query automaton
		Vd.removeAll(listRemove);

		// Add terminal vertex
		if (!checkVdt)
			Vd.add(vdt);

		// get start vertex in Vq
		VertexD vds;
		if (idStartVd >= 0)
			vds = Vd.get(idStartVd);
		else
			return false;

		// BFS to get final answer
		answer = isReachable(Vd, vds, vdt);

		// print dependence graph
		for (VertexD vd : Vd) {
			System.out.print(vd.name + ": --> ");
			for (EdgeD e : vd.neighbors)
				System.out.print(e.target.name + " | ");
			System.out.print("\n");
		}

		return answer;
	}

	public static Rvec[] localEval1(GraphQuery gq) {
		// Fragment 1 - V1
		ArrayList<Vertex> listViNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listInNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listOutNode = new ArrayList<Vertex>();
		ProcessData.LoadData("data/example/partition1.txt", listViNode,
				listInNode, listOutNode);
		Rvec[] rvset = localEval(listViNode, listInNode, listOutNode, gq);
		return rvset;
	}

	public static Rvec[] localEval2(GraphQuery gq) {
		ArrayList<Vertex> listViNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listInNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listOutNode = new ArrayList<Vertex>();
		ProcessData.LoadData("data/example/partition2.txt", listViNode,
				listInNode, listOutNode);
		Rvec[] rvset = localEval(listViNode, listInNode, listOutNode, gq);
		return rvset;
	}

	public static Rvec[] localEval3(GraphQuery gq) {
		ArrayList<Vertex> listViNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listInNode = new ArrayList<Vertex>();
		ArrayList<Vertex> listOutNode = new ArrayList<Vertex>();
		ProcessData.LoadData("data/example/partition3.txt", listViNode,
				listInNode, listOutNode);
		Rvec[] rvset = localEval(listViNode, listInNode, listOutNode, gq);
		return rvset;
	}

	public static ArrayList<String> listMarked;

	/**
	 * @param vfi
	 *            : a set of vertices in fragment i
	 * @param inodes
	 *            : a set of input node
	 * @param onodes
	 *            : a set of output node
	 * @param s
	 *            : start node in query
	 * @param t
	 *            : terminal node in query
	 * @param gq
	 *            : query automaton
	 * @return a set of vectors of the boolean formula
	 */
	public static Rvec[] localEval(ArrayList<Vertex> vfi,
			ArrayList<Vertex> inodes, ArrayList<Vertex> onodes, GraphQuery gq) {

		ArrayList<Rvec> rvset = new ArrayList<Rvec>();

		ArrayList<VertexQ> Vq = gq.Vq; // get all vertex in query
		VertexQ ut = gq.ut; // get terminal state

		Vertex s = new Vertex(gq.us.stateName); // get start vertex
		Vertex t = new Vertex(gq.ut.stateName); // get terminal vertex

		ArrayList<Vertex> iset = inodes; // set in-nodes
		ArrayList<Vertex> oset = onodes; // set virtual nodes

		if (vfi.contains(t)) {
			if (!oset.contains(t)) {
				int index = vfi.indexOf(t);
				vfi.get(index).label = t.name;
				t = vfi.get(index);
				oset.add(t);
			} else {
				int index1 = oset.indexOf(t);
				oset.get(index1).label = t.name;

				int index2 = vfi.indexOf(t);
				vfi.get(index2).label = t.name;
			}

		}

		if (vfi.contains(s) && !oset.contains(s)) {
			if (!iset.contains(s)) {
				int index = vfi.indexOf(s);
				vfi.get(index).label = s.name;
				s = vfi.get(index);
				iset.add(s);
			} else {
				int index1 = iset.indexOf(s);
				iset.get(index1).label = s.name;

				int index2 = vfi.indexOf(s);
				vfi.get(index2).label = s.name;
			}
		}

		for (Vertex v : vfi)
			v.visit = false;

		for (Vertex v : oset) {
			v.rvec = new ArrayList<Rvec>(); // set empty

			// set value for v where indicate v can match of state u
			for (VertexQ u : Vq)
				// v is terminal node
				if (v.equals(t) && u.equals(ut))
					v.rvec.add(new Rvec(v.name, u.stateName,
							new ArrayList<BoolFormula>(Arrays
									.asList(new BoolFormula(true)))));
				// v is match of state u
				else if (v.L().equals(u.Lq()))
					v.rvec.add(new Rvec(v.name, u.stateName,
							new ArrayList<BoolFormula>(Arrays
									.asList(new BoolFormula(new X(v.name,
											u.stateName))))));
				// v is not match of state u
				else
					v.rvec.add(new Rvec(v.name, u.stateName,
							new ArrayList<BoolFormula>(Arrays
									.asList(new BoolFormula(false)))));

			v.visit = true;
		}

		// compute vector boolean formula for each input node
		for (Vertex v : iset) {
			listMarked = new ArrayList<String>();
			v.rvec = cmpRvec(v, vfi, gq);
			rvset.addAll(v.rvec);
		}

		return rvset.toArray(new Rvec[rvset.size()]);
	}

	/**
	 * @param v
	 *            : input node
	 * @param vfi
	 *            : list of nodes in V
	 * @param gq
	 *            : query automaton
	 * @return: a vector Rvec of boolean formula
	 */
	public static ArrayList<Rvec> cmpRvec(Vertex v, ArrayList<Vertex> vfi,
			GraphQuery gq) {

		ArrayList<VertexQ> Vq = gq.Vq; // get all vertex in query

		if (v.visit == true)
			return v.rvec;

		listMarked.add(v.name);

		// initial false for all state by v
		for (VertexQ u : Vq)
			v.rvec.add(new Rvec(v.name, u.stateName,
					new ArrayList<BoolFormula>(Arrays.asList(new BoolFormula(
							false)))));

		// get list children node of v
		ArrayList<Vertex> childrenOfV = new ArrayList<Vertex>();
		for (Edge e : v.neighbors)
			if (!listMarked.contains(e.target)) {
				Vertex child = getVertex(e.target, vfi);
				if (child != null)
					childrenOfV.add(child);
			}

		// if v do not child, set visited
		if (childrenOfV.size() == 0)
			v.visit = true;
		else {
			// recurse visit children node and compute vector Rvec via them
			for (Vertex w : childrenOfV) {
				if (w.visit == false)
					w.rvec = cmpRvec(w, vfi, gq);

				int id = 0;
				for (VertexQ u : Vq) {
					if (v.L().equals(u.Lq())) {

						Rvec r = v.rvec.get(id);
						ArrayList<BoolFormula> list = r.value;

						if (list.get(0).value == false) {
							// compose value from children node w
							// where w match of children state of u
							ArrayList<BoolFormula> value = cmposeVec(u, w,
									w.rvec, gq);
							if (!value.isEmpty()) {

								if (list.get(0).boolVar == null)
									list.remove(0);

								for (BoolFormula bf : value)
									if (bf.boolVar != null) {
										list.add(bf);
									} else if (bf.value == true) {
										list.clear();
										list.add(bf);
									} else if (bf.boolVar == null
											&& bf.value == false)
										list.add(bf);

								v.rvec.set(id, new Rvec(v.name, u.stateName,
										list));
							}
							break;
						}

					}
					id++;
				}
				v.visit = true;
			}
		}

		return v.rvec;
	}

	/**
	 * @param u
	 *            : a state in Vq
	 * @param w
	 *            : a vertex in Vi
	 * @param wRvec
	 *            : a vector of Boolean formula of node w
	 * @return list of boolean formula
	 */
	public static ArrayList<BoolFormula> cmposeVec(VertexQ u, Vertex w,
			ArrayList<Rvec> wRvec, GraphQuery gq) {

		ArrayList<VertexQ> childrenOfU = new ArrayList<VertexQ>();
		ArrayList<BoolFormula> list = new ArrayList<BoolFormula>();

		// Get children state of u
		for (EdgeQ e : u.childrenState) {
			VertexQ child = getVertexQ(e.target, gq.Vq);
			childrenOfU.add(child);
		}

		// compose value
		for (VertexQ v : childrenOfU)
			if (w.L().equals(v.Lq())) {
				for (Rvec r : wRvec)
					if (r.u.equals(v.Lq())) {
						list = r.value;
						break;
					}
				break;
			}
		return list;
	}

	public static <T> T[] concat(T[] first, T[] second) {
		T[] result = Arrays.copyOf(first, first.length + second.length);
		System.arraycopy(second, 0, result, first.length, second.length);
		return result;
	}

	public static VertexD getVertexD(String name, ArrayList<VertexD> Vd) {
		VertexD tmp = null;
		for (VertexD v : Vd)
			if (v.name.equals(name)) {
				tmp = v;
				break;
			}

		return tmp;
	}

	public static Vertex getVertex(String name, ArrayList<Vertex> vfi) {
		Vertex tmp = null;
		for (Vertex v : vfi)
			if (v.name.equals(name)) {
				tmp = v;
				break;
			}

		return tmp;
	}

	public static VertexQ getVertexQ(String name, ArrayList<VertexQ> Vq) {
		VertexQ tmp = null;
		for (VertexQ v : Vq)
			if (v.stateName.equals(name)) {
				tmp = v;
				break;
			}
		return tmp;
	}

}
